package com.wc.blue_bridge_history.Java12Q.C_最小权值;

import java.io.PrintWriter;
import java.util.Arrays;

/**
 * @Author congge
 * @Date 2024/5/20 18:34
 * @description https://www.lanqiao.cn/problems/1563/learning/
 */
public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 2025;
    static long INF = 0x3f3f3f3fL * 0x3f3f3f3f;
    static long[] f = new long[N];

    public static void main(String[] args) {
        Arrays.fill(f, 1, N, INF);
        f[0] = 0;
        f[1] = 1;
        for (int i = 2; i <= 2021; i++) {
            for (int l = 1; l < i; l++) {
                int r = i - l - 1;
                f[i] = Math.min(f[i], 1 + 2 * f[l] + 3 * f[r] + (long) l * l * r);
            }
        }
        out.println(f[2021]);
        out.flush();
    }
}
